package main

import (
	"fmt"
	"go_dev/day5/homework4/random"
)

func partition(s []int) int {
	/* 最左边的数归位
	返回归位的下标
	*/
	left, right := 0, len(s)-1
	n := s[left]
	for left < right {
		// 内层for循环也要判断left和right是否相遇，因为外层的条件不会再每次移动后都检查
		// 但是需要每次移动后都检查，否则会下标越界
		// 比如：初始排列最小的数就在最左边的情况，right会一直减到-1
		for n <= s[right] && left < right {
			right--
		}
		// for循环外不能移动left或right，否则最后一轮会有额外的移动
		s[left] = s[right]
		for n >= s[left] && left < right {
			left++
		}
		s[right] = s[left]
	}
	s[left] = n
	return left
}

func partition2(s []int) int {
	/* 另一种归位的算法 */
	n := s[0]
	j := 0
	for i := 1; i < len(s); i++ {
		if n > s[i] {
			s[j] = s[i]
			s[i] = s[j+1]
			j++
		}
	}
	s[j] = n
	return j
}

func quick(s []int) {
	if len(s) <= 1 {
		return
	}
	mid := partition2(s)
	fmt.Println(s[0:mid], s[mid], s[mid+1:len(s)])
	quick(s[0:mid])
	quick(s[mid+1:len(s)])
}

func main(){
	s := random.RandSlice(20)
	fmt.Println(s)
	quick(s)
	fmt.Println(s)
}

